SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Goertzel algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Goertzel algorithm</span></span>

</h1>

</header>

<p>The <b>Goertzel algorithm</b> is a technique in <a href="Digital_signal_processing" title="Digital signal processing">digital signal processing</a> (DSP) for efficient evaluation of the individual terms of the <a href="Discrete_Fourier_transform" title="Discrete Fourier transform">discrete Fourier transform</a> (DFT). It is useful in certain practical applications, such as recognition of <a href="Dual-tone_multi-frequency_signaling" class="mw-redirect" title="Dual-tone multi-frequency signaling">dual-tone multi-frequency signaling</a> (DTMF) tones produced by the push buttons of the keypad of a traditional analog <a href="Telephone" title="Telephone">telephone</a>. The algorithm was first described by <a href="Gerald_Goertzel" title="Gerald Goertzel">Gerald Goertzel</a> in 1958.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>Like the DFT, the Goertzel algorithm analyses one selectable frequency component from a <a href="Discrete_signal" class="mw-redirect" title="Discrete signal">discrete signal</a>.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Unlike direct DFT calculations, the Goertzel algorithm applies a single <a href="Real_number" title="Real number">real-valued</a> coefficient at each iteration, using real-valued arithmetic for real-valued input sequences. For covering a full spectrum (except when using for continuous stream of data where coefficients are reused for subsequent calculations, which has computational complexity equivalent of <a href="Sliding_DFT" title="Sliding DFT">sliding DFT</a>), the Goertzel algorithm has a <a href="Computational_complexity_theory" title="Computational complexity theory">higher order of complexity</a> than <a href="Fast_Fourier_transform" title="Fast Fourier transform">fast Fourier transform</a> (FFT) algorithms, but for computing a small number of selected frequency components, it is more numerically efficient. The simple structure of the Goertzel algorithm makes it well suited to small processors and embedded applications.

</p><p>The Goertzel algorithm can also be used "in reverse" as a sinusoid synthesis function, which requires only 1 multiplication and 1 subtraction per generated sample.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="The_algorithm">The algorithm</h2></div>

<p>The main calculation in the Goertzel algorithm has the form of a <a href="Digital_filter" title="Digital filter">digital filter</a>, and for this reason the algorithm is often called a <i>Goertzel filter</i>. The filter operates on an input sequence <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x[n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x[n]}</annotation>

</semantics>

</math></span><img src="./864cbbefbdcb55af4d9390911de1bf70167c4a3d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.018ex; height:2.843ex;" alt="{\displaystyle x[n]}" loading="lazy"></span> in a cascade of two stages with a parameter <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \omega _{0}}</annotation>

</semantics>

</math></span><img src="./9a713d16c489051d4f515e12b1f86061c6be799b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.5ex; height:2.009ex;" alt="{\displaystyle \omega _{0}}" loading="lazy"></span>, giving the frequency to be analysed, normalised to <a href="Radian" title="Radian">radians</a> per sample.

</p><p>The first stage calculates an intermediate sequence, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s[n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s[n]}</annotation>

</semantics>

</math></span><img src="./ffe878c033cc70d1aa3ffbd156394791aa8dffde.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.779ex; height:2.843ex;" alt="{\displaystyle s[n]}" loading="lazy"></span>:

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output table.numblk{border-collapse:collapse;border:none;margin-top:0;margin-right:0;margin-bottom:0}.mw-parser-output table.numblk>tbody>tr>td{vertical-align:middle;padding:0}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2){width:99%}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table{border-collapse:collapse;margin:0;border:none;width:100%}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td:first-child,.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td:last-child{padding:0 0.4ex}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td:nth-child(2){width:100%;padding:0}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:last-child>td{padding:0}.mw-parser-output table.numblk>tbody>tr>td:last-child{font-weight:bold}.mw-parser-output table.numblk.numblk-raw-n>tbody>tr>td:last-child{font-weight:unset}.mw-parser-output table.numblk>tbody>tr>td:last-child::before{content:"("}.mw-parser-output table.numblk>tbody>tr>td:last-child::after{content:")"}.mw-parser-output table.numblk.numblk-raw-n>tbody>tr>td:last-child::before,.mw-parser-output table.numblk.numblk-raw-n>tbody>tr>td:last-child::after{content:none}.mw-parser-output table.numblk>tbody>tr>td{border:none}.mw-parser-output table.numblk.numblk-border>tbody>tr>td{border:thin solid}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td{border:none}.mw-parser-output table.numblk.numblk-border>tbody>tr>td:nth-child(2)>table>tbody>tr:first-child>td{border:thin solid}.mw-parser-output table.numblk>tbody>tr>td:nth-child(2)>table>tbody>tr:last-child>td{border-left:none;border-right:none;border-bottom:none}.mw-parser-output table.numblk.numblk-border>tbody>tr>td:nth-child(2)>table>tbody>tr:last-child>td{border-left:thin solid;border-right:thin solid;border-bottom:thin solid}.mw-parser-output table.numblk:target{color:var(--color-base,#202122);background-color:#cfe8fd}@media screen{html.skin-theme-clientpref-night .mw-parser-output table.numblk:target{color:var(--color-base,#eaecf0);background-color:#301702}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output table.numblk:target{color:var(--color-base,#eaecf0);background-color:#301702}}

/* end https://en.wikipedia.org/ */

</style><table role="presentation" class="numblk" style="margin-left: 1.6em;"><tbody><tr><td class="nowrap"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s[n]=x[n]+2\cos(\omega _{0})s[n-1]-s[n-2].}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s[n]=x[n]+2\cos(\omega _{0})s[n-1]-s[n-2].}</annotation>

</semantics>

</math></span><img src="./27963fcf59e7d04a694c325473e4b0d932569a37.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:41.756ex; height:2.843ex;" alt="{\displaystyle s[n]=x[n]+2\cos(\omega _{0})s[n-1]-s[n-2].}" loading="lazy"></span></td> <td></td> <td class="nowrap">1</td></tr></tbody></table>

<p>The second stage applies the following filter to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s[n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s[n]}</annotation>

</semantics>

</math></span><img src="./ffe878c033cc70d1aa3ffbd156394791aa8dffde.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.779ex; height:2.843ex;" alt="{\displaystyle s[n]}" loading="lazy"></span>, producing output sequence <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y[n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y[n]}</annotation>

</semantics>

</math></span><img src="./305428e6d1fb59cd0163a7a96ace52292a262afa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.844ex; height:2.843ex;" alt="{\displaystyle y[n]}" loading="lazy"></span>:

</p>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y[n]=s[n]-e^{-j\omega _{0}}s[n-1].}</annotation>

</semantics>

</math></span><img src="./f734ed42bb7c0ec73ab4b17fdee7e3fcde0fd972.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.116ex; height:3.176ex;" alt="{\displaystyle y[n]=s[n]-e^{-j\omega _{0}}s[n-1].}" loading="lazy"></span></td> <td></td> <td class="nowrap">2</td></tr></tbody></table>

<p>The first filter stage can be observed to be a second-order <a href="Infinite_impulse_response" title="Infinite impulse response">IIR filter</a> with a <a href="Digital_filter#Direct_form_I" title="Digital filter">direct-form</a> structure. This particular structure has the property that its internal state variables equal the past output values from that stage. Input values <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x[n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x[n]}</annotation>

</semantics>

</math></span><img src="./864cbbefbdcb55af4d9390911de1bf70167c4a3d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.018ex; height:2.843ex;" alt="{\displaystyle x[n]}" loading="lazy"></span> for <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n<0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n<0}</annotation>

</semantics>

</math></span><img src="./ad9f68fb8426c4411972241aac6c359e7812eaba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n<0}" loading="lazy"></span> are presumed all equal to 0. To establish the initial filter state so that evaluation can begin at sample <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x[0]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x[0]}</annotation>

</semantics>

</math></span><img src="./f1fa8bd2c3dfa6f0cec1039627bd956f8651c14c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.786ex; height:2.843ex;" alt="{\displaystyle x[0]}" loading="lazy"></span>, the filter states are assigned initial values <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s[-2]=s[-1]=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s[-2]=s[-1]=0}</annotation>

</semantics>

</math></span><img src="./426e8f5448b4c66d60147cb1176242213c5a93dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.069ex; height:2.843ex;" alt="{\displaystyle s[-2]=s[-1]=0}" loading="lazy"></span>. To avoid <a href="Aliasing" title="Aliasing">aliasing</a> hazards, frequency <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \omega _{0}}</annotation>

</semantics>

</math></span><img src="./9a713d16c489051d4f515e12b1f86061c6be799b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.5ex; height:2.009ex;" alt="{\displaystyle \omega _{0}}" loading="lazy"></span> is often restricted to the range 0 to π (see <a href="Nyquist%E2%80%93Shannon_sampling_theorem" title="Nyquist–Shannon sampling theorem">Nyquist–Shannon sampling theorem</a>); using a value outside this range is not meaningless, but is equivalent to using an aliased frequency inside this range, since the exponential function is periodic with a period of 2π in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega _{0}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \omega _{0}}</annotation>

</semantics>

</math></span><img src="./9a713d16c489051d4f515e12b1f86061c6be799b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.5ex; height:2.009ex;" alt="{\displaystyle \omega _{0}}" loading="lazy"></span>.

</p><p>The second-stage filter can be observed to be a <a href="Finite_impulse_response" title="Finite impulse response">FIR filter</a>, since its calculations do not use any of its past outputs.

</p><p><a href="Z-transform" title="Z-transform">Z-transform</a> methods can be applied to study the properties of the filter cascade. The Z transform of the first filter stage given in equation (1) is

</p>

<mtr>

<mtd>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mtd>

<mtd>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

<mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\frac {S(z)}{X(z)}}&={\frac {1}{1-2\cos(\omega _{0})z^{-1}+z^{-2}}}\\&={\frac {1}{(1-e^{+j\omega _{0}}z^{-1})(1-e^{-j\omega _{0}}z^{-1})}}.\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./fe0c94799471f579074237393cc9590e78506597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.489ex; margin-bottom: -0.182ex; width:39.768ex; height:12.509ex;" alt="{\displaystyle {\begin{aligned}{\frac {S(z)}{X(z)}}&={\frac {1}{1-2\cos(\omega _{0})z^{-1}+z^{-2}}}\\&={\frac {1}{(1-e^{+j\omega _{0}}z^{-1})(1-e^{-j\omega _{0}}z^{-1})}}.\end{aligned}}}" loading="lazy"></span></td> <td></td> <td class="nowrap">3</td></tr></tbody></table>

<p>The Z transform of the second filter stage given in equation (2) is

</p>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {Y(z)}{S(z)}}=1-e^{-j\omega _{0}}z^{-1}.}</annotation>

</semantics>

</math></span><img src="./85a479fa2bb64f0f2c7a5cf0fdfb0f0a43638408.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:21.804ex; height:6.509ex;" alt="{\displaystyle {\frac {Y(z)}{S(z)}}=1-e^{-j\omega _{0}}z^{-1}.}" loading="lazy"></span></td> <td></td> <td class="nowrap">4</td></tr></tbody></table>

<p>The combined transfer function of the cascade of the two filter stages is then

</p>

<mtr>

<mtd>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mtd>

<mtd>

<mfrac>

<mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

<mrow>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\frac {S(z)}{X(z)}}{\frac {Y(z)}{S(z)}}={\frac {Y(z)}{X(z)}}&={\frac {(1-e^{-j\omega _{0}}z^{-1})}{(1-e^{+j\omega _{0}}z^{-1})(1-e^{-j\omega _{0}}z^{-1})}}\\&={\frac {1}{1-e^{+j\omega _{0}}z^{-1}}}.\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./2d7879615ba4777893d21be78154b61a60d89f86.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.391ex; margin-bottom: -0.28ex; width:53.44ex; height:12.509ex;" alt="{\displaystyle {\begin{aligned}{\frac {S(z)}{X(z)}}{\frac {Y(z)}{S(z)}}={\frac {Y(z)}{X(z)}}&={\frac {(1-e^{-j\omega _{0}}z^{-1})}{(1-e^{+j\omega _{0}}z^{-1})(1-e^{-j\omega _{0}}z^{-1})}}\\&={\frac {1}{1-e^{+j\omega _{0}}z^{-1}}}.\end{aligned}}}" loading="lazy"></span></td> <td></td> <td class="nowrap">5</td></tr></tbody></table>

<p>This can be transformed back to an equivalent time-domain sequence, and the terms unrolled back to the first input term at index <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=0}</annotation>

</semantics>

</math></span><img src="./26819344e55f5e671c76c07c18eb4291fcec85ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n=0}" loading="lazy"></span>:

</p>

<mtr>

<mtd>

</mtd>

<mtd>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</munderover>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mrow>

</mrow>

</munderover>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

<mtext>since </mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}y[n]&=x[n]+e^{+j\omega _{0}}y[n-1]\\&=\sum _{k=-\infty }^{n}x[k]e^{+j\omega _{0}(n-k)}\\&=e^{j\omega _{0}n}\sum _{k=0}^{n}x[k]e^{-j\omega _{0}k}\qquad {\text{since }}\forall k<0,x[k]=0.\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./554568ab1166dcdd7158117fde9ebfe8ad71dcdf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -8.171ex; width:53.16ex; height:17.509ex;" alt="{\displaystyle {\begin{aligned}y[n]&=x[n]+e^{+j\omega _{0}}y[n-1]\\&=\sum _{k=-\infty }^{n}x[k]e^{+j\omega _{0}(n-k)}\\&=e^{j\omega _{0}n}\sum _{k=0}^{n}x[k]e^{-j\omega _{0}k}\qquad {\text{since }}\forall k<0,x[k]=0.\end{aligned}}}" loading="lazy"></span></td> <td></td> <td class="nowrap">6</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Numerical_stability">Numerical stability</h2></div>

<p>It can be observed that the <a href="Pole_(complex_analysis)" class="mw-redirect" title="Pole (complex analysis)">poles</a> of the filter's <a href="Z_transform" class="mw-redirect" title="Z transform">Z transform</a> are located at <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e^{+j\omega _{0}}}">

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e^{+j\omega _{0}}}</annotation>

</semantics>

</math></span><img src="./8afb7a628870916e7e1eb750a7460c5c0455a3bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.126ex; height:2.676ex;" alt="{\displaystyle e^{+j\omega _{0}}}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e^{-j\omega _{0}}}">

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e^{-j\omega _{0}}}</annotation>

</semantics>

</math></span><img src="./f93a5833f1c3b0b2d40072d62379239d8428f3b4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.126ex; height:2.676ex;" alt="{\displaystyle e^{-j\omega _{0}}}" loading="lazy"></span>, on a circle of unit radius centered on the origin of the complex Z-transform plane. This property indicates that the filter process is <a href="Marginal_stability" title="Marginal stability">marginally stable</a> and vulnerable to <a href="Numerical_stability" title="Numerical stability">numerical-error accumulation</a> when computed using low-precision arithmetic and long input sequences.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> A numerically stable version was proposed by <a href="Christian_Reinsch" title="Christian Reinsch">Christian Reinsch</a>.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="DFT_computations">DFT computations</h2></div>

<p>For the important case of computing a DFT term, the following special restrictions are applied.

</p>

<ul><li>The filtering terminates at index <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=N}</annotation>

</semantics>

</math></span><img src="./78fd6116383f2004f7dd59ff8a81ede1c2f6d3ae.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.557ex; height:2.176ex;" alt="{\displaystyle n=N}" loading="lazy"></span>, where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math></span><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></span> is the number of terms in the input sequence of the DFT.</li>

<li>The frequencies chosen for the Goertzel analysis are restricted to the special form</li></ul>

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \omega _{0}=2\pi {\frac {k}{N}}.}</annotation>

</semantics>

</math></span><img src="./42f6ec7618bea9855846a25515ccd2666d1ce65f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:11.64ex; height:5.343ex;" alt="{\displaystyle \omega _{0}=2\pi {\frac {k}{N}}.}" loading="lazy"></span></td> <td></td> <td class="nowrap">7</td></tr></tbody></table>

<ul><li>The index number <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> indicating the "frequency bin" of the DFT is selected from the set of index numbers</li></ul>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\in \{0,1,2,...,N-1\}.}</annotation>

</semantics>

</math></span><img src="./65c99e6eedc4e468f1a0bef8ba46130bc3eea2a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.815ex; height:2.843ex;" alt="{\displaystyle k\in \{0,1,2,...,N-1\}.}" loading="lazy"></span></td> <td></td> <td class="nowrap">8</td></tr></tbody></table>

<p>Making these substitutions into equation (6) and observing that the term <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e^{+j2\pi k}=1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e^{+j2\pi k}=1}</annotation>

</semantics>

</math></span><img src="./8406674bc5572bb4ef3c9b113e5a40b2942a9b68.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.153ex; height:2.676ex;" alt="{\displaystyle e^{+j2\pi k}=1}" loading="lazy"></span>, equation (6) then takes the following form:

</p>

</mrow>

</mrow>

</munderover>

<msup>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y[N]=\sum _{n=0}^{N}x[n]e^{-j2\pi {\frac {nk}{N}}}.}</annotation>

</semantics>

</math></span><img src="./7afdc48a0d2f1752e9aff43310f642706280e5b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:23.386ex; height:7.343ex;" alt="{\displaystyle y[N]=\sum _{n=0}^{N}x[n]e^{-j2\pi {\frac {nk}{N}}}.}" loading="lazy"></span></td> <td></td> <td class="nowrap">9</td></tr></tbody></table>

<p>We can observe that the right side of equation (9) is extremely similar to the defining formula for DFT term <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X[k]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X[k]}</annotation>

</semantics>

</math></span><img src="./b44d31b5739397a3a3a58892804677840e85bb2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.485ex; height:2.843ex;" alt="{\displaystyle X[k]}" loading="lazy"></span>, the DFT term for index number <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>, but not exactly the same. The summation shown in equation (9) requires <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N+1}</annotation>

</semantics>

</math></span><img src="./fdf2b9cbfe9051fd4e7b50c8028866d497eac35b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.066ex; height:2.343ex;" alt="{\displaystyle N+1}" loading="lazy"></span> input terms, but only <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math></span><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></span> input terms are available when evaluating a DFT. A simple but inelegant expedient is to extend the input sequence <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x[n]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x[n]}</annotation>

</semantics>

</math></span><img src="./864cbbefbdcb55af4d9390911de1bf70167c4a3d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.018ex; height:2.843ex;" alt="{\displaystyle x[n]}" loading="lazy"></span> with one more artificial value <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x[N]=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x[N]=0}</annotation>

</semantics>

</math></span><img src="./b53e70a8d74d717f7ab94d8bf15efc753846cc6c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.948ex; height:2.843ex;" alt="{\displaystyle x[N]=0}" loading="lazy"></span>.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> We can see from equation (9) that the mathematical effect on the final result is the same as removing term <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x[N]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x[N]}</annotation>

</semantics>

</math></span><img src="./63304547af2f7774e1be9669e1169de8b33285fd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.687ex; height:2.843ex;" alt="{\displaystyle x[N]}" loading="lazy"></span> from the summation, thus delivering the intended DFT value.

</p><p>However, there is a more elegant approach that avoids the extra filter pass. From equation (1), we can note that when the extended input term <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x[N]=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x[N]=0}</annotation>

</semantics>

</math></span><img src="./b53e70a8d74d717f7ab94d8bf15efc753846cc6c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.948ex; height:2.843ex;" alt="{\displaystyle x[N]=0}" loading="lazy"></span> is used in the final step,

</p>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s[N]=2\cos(\omega _{0})s[N-1]-s[N-2].}</annotation>

</semantics>

</math></span><img src="./78add7d4190eabf99f04ee86272479ae196a45f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:36.905ex; height:2.843ex;" alt="{\displaystyle s[N]=2\cos(\omega _{0})s[N-1]-s[N-2].}" loading="lazy"></span></td> <td></td> <td class="nowrap">10</td></tr></tbody></table>

<p>Thus, the algorithm can be completed as follows:

</p>

<ul><li>terminate the IIR filter after processing input term <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x[N-1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x[N-1]}</annotation>

</semantics>

</math></span><img src="./5c94aff4cd414227041fbd183f958a43499ac7d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.69ex; height:2.843ex;" alt="{\displaystyle x[N-1]}" loading="lazy"></span>,</li>

<li>apply equation (10) to construct <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s[N]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s[N]}</annotation>

</semantics>

</math></span><img src="./d181d4e3e900fdbe7cbc818969e3b1d25dd4a446.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.448ex; height:2.843ex;" alt="{\displaystyle s[N]}" loading="lazy"></span> from the prior outputs <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s[N-1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s[N-1]}</annotation>

</semantics>

</math></span><img src="./ddc039e54ef590d6a907fbfb8552aaae44733c23.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.451ex; height:2.843ex;" alt="{\displaystyle s[N-1]}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s[N-2]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s[N-2]}</annotation>

</semantics>

</math></span><img src="./5b24f39099d3ec38928b50c67d8a62ca43549231.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.451ex; height:2.843ex;" alt="{\displaystyle s[N-2]}" loading="lazy"></span>,</li>

<li>apply equation (2) with the calculated <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s[N]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s[N]}</annotation>

</semantics>

</math></span><img src="./d181d4e3e900fdbe7cbc818969e3b1d25dd4a446.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.448ex; height:2.843ex;" alt="{\displaystyle s[N]}" loading="lazy"></span> value and with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s[N-1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s[N-1]}</annotation>

</semantics>

</math></span><img src="./ddc039e54ef590d6a907fbfb8552aaae44733c23.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.451ex; height:2.843ex;" alt="{\displaystyle s[N-1]}" loading="lazy"></span> produced by the final direct calculation of the filter.</li></ul>

<p>The last two mathematical operations are simplified by combining them algebraically:

</p>

<mtr>

<mtd>

</mtd>

<mtd>

<msup>

<mfrac>

</mfrac>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msup>

<mfrac>

</mfrac>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

<mfrac>

</mfrac>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}y[N]&=s[N]-e^{-j2\pi {\frac {k}{N}}}s[N-1]\\&=(2\cos(\omega _{0})s[N-1]-s[N-2])-e^{-j2\pi {\frac {k}{N}}}s[N-1]\\&=e^{j2\pi {\frac {k}{N}}}s[N-1]-s[N-2].\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./4cc5e858f5999c11b56059a70d6ca78368e6cf5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.838ex; width:57.231ex; height:12.676ex;" alt="{\displaystyle {\begin{aligned}y[N]&=s[N]-e^{-j2\pi {\frac {k}{N}}}s[N-1]\\&=(2\cos(\omega _{0})s[N-1]-s[N-2])-e^{-j2\pi {\frac {k}{N}}}s[N-1]\\&=e^{j2\pi {\frac {k}{N}}}s[N-1]-s[N-2].\end{aligned}}}" loading="lazy"></span></td> <td></td> <td class="nowrap">11</td></tr></tbody></table>

<p>Note that stopping the filter updates at term <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N-1}</annotation>

</semantics>

</math></span><img src="./86aeb216b214f70df1341f34ce273cd3582ce2aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.066ex; height:2.343ex;" alt="{\displaystyle N-1}" loading="lazy"></span> and immediately applying equation (2) rather than equation (11) misses the final filter state updates, yielding a result with incorrect phase.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>

</p><p>The particular filtering structure chosen for the Goertzel algorithm is the key to its efficient DFT calculations. We can observe that only one output value <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y[N]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y[N]}</annotation>

</semantics>

</math></span><img src="./a41cb408346f831e35a31685137996f1a3372328.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.513ex; height:2.843ex;" alt="{\displaystyle y[N]}" loading="lazy"></span> is used for calculating the DFT, so calculations for all the other output terms are omitted. Since the FIR filter is not calculated, the IIR stage calculations <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s[0],s[1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s[0],s[1]}</annotation>

</semantics>

</math></span><img src="./c1950bdacd66f41d960ed3b110ffe31af8339a0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.127ex; height:2.843ex;" alt="{\displaystyle s[0],s[1]}" loading="lazy"></span>, etc. can be discarded immediately after updating the first stage's internal state.

</p><p>This seems to leave a paradox: to complete the algorithm, the FIR filter stage must be evaluated once using the final two outputs from the IIR filter stage, while for computational efficiency the IIR filter iteration discards its output values. This is where the properties of the direct-form filter structure are applied. The two internal state variables of the IIR filter provide the last two values of the IIR filter output, which are the terms required to evaluate the FIR filter stage.

</p>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Power-spectrum_terms">Power-spectrum terms</h3></div>

<p>Examining equation (6), a final IIR filter pass to calculate term <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y[N]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y[N]}</annotation>

</semantics>

</math></span><img src="./a41cb408346f831e35a31685137996f1a3372328.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.513ex; height:2.843ex;" alt="{\displaystyle y[N]}" loading="lazy"></span> using a supplemental input value <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x[N]=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x[N]=0}</annotation>

</semantics>

</math></span><img src="./b53e70a8d74d717f7ab94d8bf15efc753846cc6c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.948ex; height:2.843ex;" alt="{\displaystyle x[N]=0}" loading="lazy"></span> applies a complex multiplier of magnitude 1 to the previous term <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y[N-1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y[N-1]}</annotation>

</semantics>

</math></span><img src="./2c9207272b125a05ff024290e1f5ee969d016739.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.516ex; height:2.843ex;" alt="{\displaystyle y[N-1]}" loading="lazy"></span>. Consequently, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y[N]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y[N]}</annotation>

</semantics>

</math></span><img src="./a41cb408346f831e35a31685137996f1a3372328.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.513ex; height:2.843ex;" alt="{\displaystyle y[N]}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y[N-1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y[N-1]}</annotation>

</semantics>

</math></span><img src="./2c9207272b125a05ff024290e1f5ee969d016739.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.516ex; height:2.843ex;" alt="{\displaystyle y[N-1]}" loading="lazy"></span> represent equivalent signal power. It is equally valid to apply equation (11) and calculate the signal power from term <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y[N]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y[N]}</annotation>

</semantics>

</math></span><img src="./a41cb408346f831e35a31685137996f1a3372328.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.513ex; height:2.843ex;" alt="{\displaystyle y[N]}" loading="lazy"></span> or to apply equation (2) and calculate the signal power from term <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y[N-1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y[N-1]}</annotation>

</semantics>

</math></span><img src="./2c9207272b125a05ff024290e1f5ee969d016739.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.516ex; height:2.843ex;" alt="{\displaystyle y[N-1]}" loading="lazy"></span>. Both cases lead to the following expression for the signal power represented by DFT term <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X[k]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X[k]}</annotation>

</semantics>

</math></span><img src="./b44d31b5739397a3a3a58892804677840e85bb2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.485ex; height:2.843ex;" alt="{\displaystyle X[k]}" loading="lazy"></span>:

</p>

<mtr>

<mtd>

<msup>

</msup>

</mtd>

<mtd>

<msup>

</msup>

<msup>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}X[k]\,X'[k]&=y[N]\,y'[N]=y[N-1]\,y'[N-1]\\&=s^{2}[N-1]+s^{2}[N-2]-2\cos \left(2\pi {\frac {k}{N}}\right)\,s[N-1]\,s[N-2].\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./407f08d1ca60dceb62c6a65604bb6964291c9c52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.788ex; margin-bottom: -0.217ex; width:70.397ex; height:9.176ex;" alt="{\displaystyle {\begin{aligned}X[k]\,X'[k]&=y[N]\,y'[N]=y[N-1]\,y'[N-1]\\&=s^{2}[N-1]+s^{2}[N-2]-2\cos \left(2\pi {\frac {k}{N}}\right)\,s[N-1]\,s[N-2].\end{aligned}}}" loading="lazy"></span></td> <td></td> <td class="nowrap">12</td></tr></tbody></table>

<p>In the <a href="Pseudocode" title="Pseudocode">pseudocode</a> below, the complex-valued input data is stored in the <a href="Array_data_type" class="mw-redirect" title="Array data type">array</a> <code>x</code> and the variables <code>sprev</code> and <code>sprev2</code> temporarily store output history from the IIR filter. <code>Nterms</code> is the number of samples in the array, and <code>Kterm</code> corresponds to the frequency of interest, multiplied by the sampling period.

</p>

<pre>Nterms defined here

Kterm selected here

ω = 2 × π × Kterm / Nterms;

coeff := 2 × cos(ω)

sprev := 0

sprev2 := 0

<b>for each</b> index <i>n</i> in range 0 to Nterms-1 <b>do</b>

s := x[n] + coeff × sprev - sprev2

sprev2 := sprev

sprev := s

power := sprev<sup><i>2</i></sup> + sprev2<sup><i>2</i></sup> - (coeff × sprev × sprev2)

</pre>

<p>It is possible<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> to organise the computations so that incoming samples are delivered singly to a <a href="Object-oriented_programming" title="Object-oriented programming">software object</a> that maintains the filter state between updates, with the final power result accessed after the other processing is done.

</p>

<div class="mw-heading mw-heading3"><h3 id="Single_DFT_term_with_real-valued_arithmetic">Single DFT term with real-valued arithmetic</h3></div>

<p>The case of real-valued input data arises frequently, especially in embedded systems where the input streams result from direct measurements of physical processes. When the input data are real-valued, the filter internal state variables <code>sprev</code> and <code>sprev2</code> can be observed also to be real-valued, consequently, no complex arithmetic is required in the first IIR stage. Optimizing for real-valued arithmetic typically is as simple as applying appropriate real-valued data types for the variables.

</p><p>After the calculations using input term <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x[N-1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x[N-1]}</annotation>

</semantics>

</math></span><img src="./5c94aff4cd414227041fbd183f958a43499ac7d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.69ex; height:2.843ex;" alt="{\displaystyle x[N-1]}" loading="lazy"></span>, and filter iterations are terminated, equation (11) must be applied to evaluate the DFT term. The final calculation uses complex-valued arithmetic, but this can be converted into real-valued arithmetic by separating real and imaginary terms:

</p>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}c_{r}&=\cos(2\pi {\tfrac {k}{N}}),\\c_{i}&=\sin(2\pi {\tfrac {k}{N}}),\\y[N]&=c_{r}s[N-1]-s[N-2]+jc_{i}s[N-1].\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./3e6d01ed423b7dc2c0caa949b0371a7201b80996.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.838ex; width:44.787ex; height:10.843ex;" alt="{\displaystyle {\begin{aligned}c_{r}&=\cos(2\pi {\tfrac {k}{N}}),\\c_{i}&=\sin(2\pi {\tfrac {k}{N}}),\\y[N]&=c_{r}s[N-1]-s[N-2]+jc_{i}s[N-1].\end{aligned}}}" loading="lazy"></span></td> <td></td> <td class="nowrap">13</td></tr></tbody></table>

<p>Comparing to the power-spectrum application, the only difference are the calculation used to finish:

</p>

<pre>(Same IIR filter calculations as in the signal power implementation)

XKreal = sprev * cr - sprev2;

XKimag = sprev * ci;

</pre>

<div class="mw-heading mw-heading3"><h3 id="Phase_detection">Phase detection</h3></div>

<p>This application requires the same evaluation of DFT term <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X[k]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X[k]}</annotation>

</semantics>

</math></span><img src="./b44d31b5739397a3a3a58892804677840e85bb2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.485ex; height:2.843ex;" alt="{\displaystyle X[k]}" loading="lazy"></span>, as discussed in the previous section, using a real-valued or complex-valued input stream. Then the signal phase can be evaluated as

</p>

<msup>

</mrow>

</msup>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \phi =\tan ^{-1}{\frac {\Im (X[k])}{\Re (X[k])}},}</annotation>

</semantics>

</math></span><img src="./e46b68c07207e198c580d5934151dcbb7f257c0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:20.265ex; height:6.509ex;" alt="{\displaystyle \phi =\tan ^{-1}{\frac {\Im (X[k])}{\Re (X[k])}},}" loading="lazy"></span></td> <td></td> <td class="nowrap">14</td></tr></tbody></table>

<p>taking appropriate precautions for singularities, quadrant, and so forth when computing the inverse tangent function.

</p>

<div class="mw-heading mw-heading3"><h3 id="Complex_signals_in_real_arithmetic">Complex signals in real arithmetic</h3></div>

<p>Since complex signals decompose linearly into real and imaginary parts, the Goertzel algorithm can be computed in real arithmetic separately over the sequence of real parts, yielding <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{\text{r}}[n]}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{\text{r}}[n]}</annotation>

</semantics>

</math></span><img src="./ea4a37c6483110ea44593ae3ea0b532629e47651.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.704ex; height:2.843ex;" alt="{\displaystyle y_{\text{r}}[n]}" loading="lazy"></span>, and over the sequence of imaginary parts, yielding <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{\text{i}}[n]}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{\text{i}}[n]}</annotation>

</semantics>

</math></span><img src="./cff3d89516287210e4d5ad52fa8fe7f92be8e811.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.517ex; height:2.843ex;" alt="{\displaystyle y_{\text{i}}[n]}" loading="lazy"></span>. After that, the two complex-valued partial results can be recombined:

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y[n]=y_{\text{r}}[n]+jy_{\text{i}}[n].}</annotation>

</semantics>

</math></span><img src="./c8b2b8a6909734f8ced545e035b52246d013f6da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.609ex; height:2.843ex;" alt="{\displaystyle y[n]=y_{\text{r}}[n]+jy_{\text{i}}[n].}" loading="lazy"></span></td> <td></td> <td class="nowrap">15</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Computational_complexity">Computational complexity</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<ul><li>According to <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>, computing a set of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math></span><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"></span> DFT terms using <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math></span><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"></span> applications of the Goertzel algorithm on a data set with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math></span><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></span> values with a "cost per operation" of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math></span><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"></span> has <a href="Big_O_notation" title="Big O notation">complexity</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(KNM)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(KNM)}</annotation>

</semantics>

</math></span><img src="./b6abe22467c1a0e7c7e3c59a592a932d19a98c3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.154ex; height:2.843ex;" alt="{\displaystyle O(KNM)}" loading="lazy"></span>.</li></ul>

<dl><dd>To compute a single <a href="Discrete_Fourier_transform" title="Discrete Fourier transform">DFT</a> bin <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X(f)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle X(f)}</annotation>

</semantics>

</math></span><img src="./7e865b84e1e716c652b502715a0b9376e7032993.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.068ex; height:2.843ex;" alt="{\displaystyle X(f)}" loading="lazy"></span> for a complex input sequence of length <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math></span><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></span>, the Goertzel algorithm requires <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2N}</annotation>

</semantics>

</math></span><img src="./eacbd5b0e609e1f3d7da751ac0d50113d27d22aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.226ex; height:2.176ex;" alt="{\displaystyle 2N}" loading="lazy"></span> multiplications and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 4\ N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 4\ N}</annotation>

</semantics>

</math></span><img src="./21553b45ebd0e31530d0e0af31357c1c5e63ad39.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.807ex; height:2.176ex;" alt="{\displaystyle 4\ N}" loading="lazy"></span> additions/subtractions within the loop, as well as 4 multiplications and 4 final additions/subtractions, for a total of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2N+4}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2N+4}</annotation>

</semantics>

</math></span><img src="./ac557b316892acdfd3951dfea404bd9c1f4b9589.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.229ex; height:2.343ex;" alt="{\displaystyle 2N+4}" loading="lazy"></span> multiplications and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 4N+4}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 4N+4}</annotation>

</semantics>

</math></span><img src="./5b17d9eebf1d1f052233a91a966a639e1c31883f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.229ex; height:2.343ex;" alt="{\displaystyle 4N+4}" loading="lazy"></span> additions/subtractions. This is repeated for each of the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math></span><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"></span> frequencies.</dd></dl>

<ul><li>In contrast, using an <a href="Fast_Fourier_transform" title="Fast Fourier transform">FFT</a> on a data set with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math></span><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></span> values has complexity <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(KN\log _{2}(N))}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(KN\log _{2}(N))}</annotation>

</semantics>

</math></span><img src="./3d77b3ec8dd913ead6fa3c8ef01af2f6775374d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.998ex; height:2.843ex;" alt="{\displaystyle O(KN\log _{2}(N))}" loading="lazy"></span>.</li></ul>

<dl><dd>This is harder to apply directly because it depends on the FFT algorithm used, but a typical example is a radix-2 FFT, which requires <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2\log _{2}(N)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\log _{2}(N)}</annotation>

</semantics>

</math></span><img src="./3129e5981a7bde695a4d72e08b85f4fae3755d3c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.448ex; height:2.843ex;" alt="{\displaystyle 2\log _{2}(N)}" loading="lazy"></span> multiplications and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 3\log _{2}(N)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3\log _{2}(N)}</annotation>

</semantics>

</math></span><img src="./3020ff38bde00781ac5e67cb14e496fd96138e76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.448ex; height:2.843ex;" alt="{\displaystyle 3\log _{2}(N)}" loading="lazy"></span> additions/subtractions per <a href="Discrete_Fourier_transform" title="Discrete Fourier transform">DFT</a> bin, for each of the <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math></span><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></span> bins.</dd></dl>

<p>In the complexity order expressions, when the number of calculated terms <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math></span><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"></span> is smaller than <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log N}</annotation>

</semantics>

</math></span><img src="./54e31347d160d1e54a70f79b23038030f33b6bf0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.422ex; height:2.509ex;" alt="{\displaystyle \log N}" loading="lazy"></span>, the advantage of the Goertzel algorithm is clear. But because FFT code is comparatively complex,

the "cost per unit of work" factor <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math></span><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"></span> is often larger for an FFT, and the practical advantage favours the Goertzel algorithm even for <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math></span><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"></span> several times larger than <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}(N)}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \log _{2}(N)}</annotation>

</semantics>

</math></span><img src="./eb1acd4b84984958946858fd1dc7385dc38af586.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.899ex; height:2.843ex;" alt="{\displaystyle \log _{2}(N)}" loading="lazy"></span>.

</p><p>As a rule-of-thumb for determining whether a radix-2 FFT or a Goertzel algorithm is more efficient, adjust the number of terms <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math></span><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></span> in the data set upward to the nearest exact power of 2, calling this <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{2}}</annotation>

</semantics>

</math></span><img src="./597ea9dac049261fdda77c5176b050e6588d6bb9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.92ex; height:2.509ex;" alt="{\displaystyle N_{2}}" loading="lazy"></span>, and the Goertzel algorithm is likely to be faster if

</p>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M\leq {\frac {5N_{2}}{6N}}\log _{2}(N_{2})}</annotation>

</semantics>

</math></span><img src="./fa6dc8ccd2e30345d4d8a3a868e41db1e1524e85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:19.603ex; height:5.343ex;" alt="{\displaystyle M\leq {\frac {5N_{2}}{6N}}\log _{2}(N_{2})}" loading="lazy"></span></dd></dl>

<p>FFT implementations and processing platforms have a significant impact on the relative performance. Some FFT implementations<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> perform internal complex-number calculations to generate coefficients on-the-fly, significantly increasing their "cost K per unit of work." FFT and DFT algorithms can use tables of pre-computed coefficient values for better numerical efficiency, but this requires more accesses to coefficient values buffered in external memory, which can lead to increased cache contention that counters some of the numerical advantage.

</p><p>Both algorithms gain approximately a factor of 2 efficiency when using real-valued rather than complex-valued input data. However, these gains are natural for the Goertzel algorithm but will not be achieved for the FFT without using certain algorithm variants specialised for <a href="Fast_Fourier_transform" title="Fast Fourier transform">transforming real-valued data</a>.

</p>

<ul><li><a href="Bluestein's_FFT_algorithm" class="mw-redirect" title="Bluestein's FFT algorithm">Bluestein's FFT algorithm</a> (chirp-Z)</li>

<li><a href="Frequency-shift_keying" title="Frequency-shift keying">Frequency-shift keying</a> (FSK)</li>

<li><a href="Phase-shift_keying" title="Phase-shift keying">Phase-shift keying</a> (PSK)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist reflist-columns references-column-width" style="column-width: 30em;">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFGoertzel1958" class="citation cs2">Goertzel, G. (January 1958), "An Algorithm for the Evaluation of Finite Trigonometric Series", <i>American Mathematical Monthly</i>, <b>65</b> (1): <span class="nowrap">34–</span>35, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2310304">10.2307/2310304</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2310304">2310304</a></cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFMock1985" class="citation cs2">Mock, P. (March 21, 1985), <a rel="nofollow" class="external text" href="https://focus.ti.com/lit/an/spra168/spra168.pdf">"Add DTMF Generation and Decoding to DSP-μP Designs"</a> <span class="cs1-format">(PDF)</span>, <i>EDN</i>, <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0012-7515">0012-7515</a></cite>; also found in DSP Applications with the TMS320 Family, Vol. 1, Texas Instruments, 1989.</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFChen1996" class="citation cs2">Chen, Chiouguey J. (June 1996), <a rel="nofollow" class="external text" href="https://focus.ti.com/lit/an/spra066/spra066.pdf"><i>Modified Goertzel Algorithm in DTMF Detection Using the TMS320C80 DSP</i></a> <span class="cs1-format">(PDF)</span>, Application Report, Texas Instruments, SPRA066</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFSchmer2000" class="citation cs2">Schmer, Gunter (May 2000), <a rel="nofollow" class="external text" href="https://focus.ti.com/lit/an/spra096a/spra096a.pdf"><i>DTMF Tone Generation and Detection: An Implementation Using the TMS320C54x</i></a> <span class="cs1-format">(PDF)</span>, Application Report, Texas Instruments, SPRA096a</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFChengHudak2009" class="citation cs2">Cheng, Eric; Hudak, Paul (January 2009), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170328022024/http://haskell.cs.yale.edu/wp-content/uploads/2011/01/AudioProc-TR.pdf"><i>Audio Processing and Sound Synthesis in Haskell</i></a> <span class="cs1-format">(PDF)</span>, archived from <a rel="nofollow" class="external text" href="http://haskell.cs.yale.edu/wp-content/uploads/2011/01/AudioProc-TR.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2017-03-28</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFGentleman1969" class="citation journal cs1">Gentleman, W. M. (1 February 1969). <a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fcomjnl%2F12.2.160">"An error analysis of Goertzel's (Watt's) method for computing Fourier coefficients"</a>. <i>The Computer Journal</i>. <b>12</b> (2): <span class="nowrap">160–</span>164. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fcomjnl%2F12.2.160">10.1093/comjnl/12.2.160</a></span>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFStoerBulirsch2002" class="citation cs2">Stoer, J.; Bulirsch, R. (2002), <i>Introduction to Numerical Analysis</i>, Springer, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780387954523</bdi></cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://cnx.org/content/m12024/latest/">"Goertzel's Algorithm"</a>. Cnx.org. 2006-09-12<span class="reference-accessdate">. Retrieved <span class="nowrap">2014-02-03</span></span>.</cite></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.eetimes.com/design/signal-processing-dsp/4024443/The-Goertzel-Algorithm">"Electronic Engineering Times | Connecting the Global Electronics Community"</a>. EE Times<span class="reference-accessdate">. Retrieved <span class="nowrap">2014-02-03</span></span>.</cite></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite id="CITEREFElmenreich2011" class="citation web cs1">Elmenreich, Wilfried (August 25, 2011). <a rel="nofollow" class="external text" href="https://netwerkt.wordpress.com/2011/08/25/goertzel-filter/">"Efficiently detecting a frequency using a Goertzel filter"</a><span class="reference-accessdate">. Retrieved <span class="nowrap">16 September</span> 2014</span>.</cite></span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><cite id="CITEREFPressFlanneryTeukolskyVetterling2007" class="citation cs2">Press; Flannery; Teukolsky; Vetterling (2007), "Chapter 12", <i>Numerical Recipes, The Art of Scientific Computing</i>, Cambridge University Press</cite></span>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite class="citation cs2">Proakis, J. G.; Manolakis, D. G. (1996), <i>Digital Signal Processing: Principles, Algorithms, and Applications</i>, Upper Saddle River, NJ: Prentice Hall, pp. <span class="nowrap">480–</span>481, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1996dspp.book.....P">1996dspp.book.....P</a></cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20180628024641/http://en.dsplib.org/content/goertzel/goertzel.html">Goertzel Algorithm</a> at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a> (archived 2018-06-28)</li>

<li><a rel="nofollow" class="external text" href="https://www.embedded.com/design/configurable-systems/4006427/A-DSP-algorithm-for-frequency-analysis">A DSP algorithm for frequency analysis</a></li>

<li><a rel="nofollow" class="external text" href="https://www.embedded.com/the-goertzel-algorithm">The Goertzel Algorithm by Kevin Banks</a></li>

<li><a rel="nofollow" class="external text" href="https://www.beis.de/Elektronik/Filter/Goertzel/Goertzel_en.html">Analysis of the Goertzel Algorithm by Uwe Beis</a> in which he compares it to analog 2nd order <a href="Chebyshev_filter" title="Chebyshev filter"> Chebyshev low pass filter</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-28" href="https://en.wikipedia.org/wiki/?title=Goertzel_algorithm&oldid=1297783701">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>